import java.util.Arrays;

public class SolutionOffer29 {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length==0){
            return new int[0];
        }
        int[] ans=new int[matrix.length*matrix[0].length];
        int m=matrix.length,n=matrix[0].length;
        int[] dx=new int[]{0,1,0,-1};
        int[] dy=new int[]{1,0,-1,0};
        int d=0,cx=0,cy=-1;
        for (int i=1;i<=m*n;i++){
            while (!valid(cx+dx[d],cy+dy[d],m,n) || matrix[cx+dx[d]][cy+dy[d]]==-200){
                d=(d+1)%4;
            }
            cx=cx+dx[d];
            cy=cy+dy[d];
            ans[i-1]=matrix[cx][cy];
            matrix[cx][cy]=-200;
        }
        return ans;
    }

    boolean valid(int x,int y,int m,int n){
        return x>=0 && x<m && y>=0 && y<n;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new SolutionOffer29().spiralOrder(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}})));
    }
}
